import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

// 力扣373. 查找和最小的 K 对数字
class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> result = new ArrayList<>();
        // 处理边界情况
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0 || k <= 0) {
            return result;
        }

        // 最小堆，存储三元组 [nums1[i] + nums2[j], i, j]
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int n1 = nums1.length, n2 = nums2.length;

        // 初始化：将 (nums1[i], nums2[0]) 对于每个i加入堆
        for (int i = 0; i < Math.min(n1, k); i++) {
            minHeap.offer(new int[]{nums1[i] + nums2[0], i, 0});
        }

        while (!minHeap.isEmpty() && result.size() < k) {
            int[] current = minHeap.poll();
            int i = current[1];
            int j = current[2];
            result.add(Arrays.asList(nums1[i], nums2[j]));

            // 将当前i对应的下一个j加入候选
            if (j + 1 < n2) {
                minHeap.offer(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
            }
        }

        return result;
    }
}



// 力扣190. 颠倒二进制位
class Solution1 {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            // 1. 将结果左移一位，腾出最低位的位置
            res <<= 1;
            // 2. 取出n的最低位的值，并放到res的最低位上
            res |= (n & 1);
            // 3. 将n无符号右移一位，准备处理下一位
            //     使用 >>> 防止符号扩展影响
            n >>>= 1;
        }
        return res;
    }
}